﻿/**
 * @file std_rbtree.inl
 * Copyright (c) 2019 Gaaagaa. All rights reserved.
 * 
 * @author  : Gaaagaa
 * @date    : 2019-09-09
 * @version : 1.0.0.0
 * @brief   : 定义 红黑树容器 内部相关数据类型、常量、宏 等。
 */

/**
 * The MIT License (MIT)
 * Copyright (c) Gaaagaa. All rights reserved.
 * 
 * Permission is hereby granted, free of charge, to any person obtaining a copy of
 * this software and associated documentation files (the "Software"), to deal in
 * the Software without restriction, including without limitation the rights to
 * use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
 * of the Software, and to permit persons to whom the Software is furnished to do
 * so, subject to the following conditions:
 * 
 * The above copyright notice and this permission notice shall be included in all
 * copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS
 * FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR
 * COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
 * IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 */

#ifndef __STD_RBTREE_INL__
#define __STD_RBTREE_INL__

#ifndef __STD_RBTREE_H__
#error "Please include std_rbtree.h before this file."
#endif // __STD_RBTREE_H__

#include "std_comm.inl"

////////////////////////////////////////////////////////////////////////////////
// xstd_rbtree_t 的相关数据定义

/**
 * @enum  xrbt_color_t
 * @brief 红黑树节点的 颜色 标识枚举值。
 */
typedef enum xrbt_color_t
{
    XCLR_RED   = 0,  ///< 红色 标识
    XCLR_BLACK = 1,  ///< 黑色 标识
} xrbt_color_t;

/**
 * @enum  xrbt_dock_pos_t
 * @brief 节点可停靠的相关位置枚举常量值。
 */
typedef enum xrbt_dock_pos_t
{
    XDPOS_NONE  = 0,  ///< 不可停靠
    XDPOS_LEFT  = 1,  ///< 可左侧停靠
    XDPOS_RIGHT = 2,  ///< 可右侧停靠
} xrbt_dpos_t;

/** 节点结构体中的 颜色值 字段位域数量 */
#define XRBT_CLR_FS   (8)

/** 节点结构体中的 节点元素对象缓存大小 字段位域数量 */
#define XRBT_ELM_FS   ((8 * sizeof(xrbt_size_t)) - XRBT_CLR_FS)

/** 节点元素对象缓存的最大值 */
#define XRBT_MAX_ESIZE ((((xrbt_size_t)1) << XRBT_ELM_FS) - 1)

/** 节点元素对象缓存是否与 节点缓存 分离 */
#define XRBT_ELEM_SEPARATED 0

/**
 * @struct xrbt_node_t
 * @brief  红黑树容器所使用的节点结构体描述信息。
 */
typedef struct xrbt_node_t
{
    xrbt_size_t   xst_color : XRBT_CLR_FS;  ///< 颜色值
    xrbt_size_t   xst_ksize : XRBT_ELM_FS;  ///< 节点元素对象的缓存大小（对于 NIL 节点，该值始终为 0）
    xrbt_iter_t   xiter_parent; ///< 父节点
    xrbt_iter_t   xiter_left;   ///< 左子树
    xrbt_iter_t   xiter_right;  ///< 右子树

#if (XSTD_DEBUG_LEVEL >= XSTD_DEBUG_LOWER)
    xrbt_this_t xrbt_owner;   ///< 节点所属的红黑树（用于调试时的断言判断）
#endif // XSTD_DEBUG_LOWER

#if XRBT_ELEM_SEPARATED

    xrbt_elem_t   xrbt_elem;    ///< 所存储的节点元素对象

#else // !XRBT_ELEM_SEPARATED

#ifdef _MSC_VER
#pragma warning(disable:4200)
#endif // _MSC_VER
    xstd_byte_t   xrbt_elem[0]; ///< 所存储的节点元素对象
#ifdef _MSC_VER
#pragma warning(default:4200)
#endif // _MSC_VER

#endif // XRBT_ELEM_SEPARATED

} xrbt_node_t;

/**
 * @struct xrbt_nil_t
 * @brief  红黑树容器所使用的 nil 节点结构体描述信息（其继承自 xrbt_node_t ）。
 */
typedef struct xrbt_nil_t
{
    xrbt_size_t   xst_color : XRBT_CLR_FS;  ///< 颜色值
    xrbt_size_t   xst_ksize : XRBT_ELM_FS;  ///< 节点元素对象的缓存大小（对于 NIL 节点，该值始终为 0）
    xrbt_iter_t   xiter_parent; ///< 父节点
    xrbt_iter_t   xiter_left;   ///< 左子树
    xrbt_iter_t   xiter_right;  ///< 右子树
    xrbt_this_t   xrbt_owner;   ///< 指向所属红黑树
} xrbt_nil_t;

/**
 * @struct xstd_rbtree_t
 * @brief  红黑树容器的结构体描述信息。
 */
typedef struct xstd_rbtree_t
{
    xstd_context_t  xstd_ectxt;   ///< 节点元素的类型上下文描述信息

    xrbt_kcmpfunc_t xfunc_kcmp;   ///< 节点比较操作 的回调函数
    xrbt_size_t     xrbt_csize;   ///< 当前节点数量

    xrbt_nil_t      xnode_nil;    ///< nil 节点
    xrbt_iter_t     xiter_root;   ///< 根节点
    xrbt_iter_t     xiter_lnode;  ///< 最左侧节点
    xrbt_iter_t     xiter_rnode;  ///< 最右侧节点
} xstd_rbtree_t;

/** 定义 @see rbtree_dpos_root() 与 @see rbtree_dpos_hint() 共用的函数类型名 */
typedef xrbt_iter_t (* xrbt_fdpos_t)(
    xrbt_this_t, xrbt_elem_t, xrbt_iter_t, xrbt_dpos_t *);

////////////////////////////////////////////////////////////////////////////////
// xstd_rbtree_t 的相关操作宏函数

//====================================================================

#define XRBT_ECTXT(xrbt_this)   XSTD_ECTXT(xrbt_this)
#define XRBT_ETYPE(xrbt_this)   XSTD_ETYPE(xrbt_this)
#define XRBT_ESIZE(xrbt_this)   XSTD_ESIZE(xrbt_this)
#define XRBT_ALTOR(xrbt_this)   XSTD_ALTOR(xrbt_this)

#define XRBT_MALLOC(xrbt_this, xst_size)            \
            XSTD_MALLOC((xrbt_this), (xst_size))

#define XRBT_DEALLOC(xrbt_this, xmt_mptr)           \
            XSTD_DEALLOC((xrbt_this), (xmt_mptr))

#define XRBT_ALFROM(xrbt_this, xet_dptr, xet_sptr)  \
            XSTD_ALFROM((xrbt_this), (xet_dptr), (xet_sptr))

#define XRBT_ALMOVE(xrbt_this, xet_dptr, xet_sptr)  \
            XSTD_ALMOVE((xrbt_this), (xet_dptr), (xet_sptr))

#define XRBT_ALDEST(xrbt_this, xet_elem)            \
            XSTD_ALDEST((xrbt_this), (xet_elem))

#define XRBT_ISSAME_TYPE(xrbt_lthis, xrbt_rthis)    \
            XSTD_ISSAME_TYPE((xrbt_lthis), (xrbt_rthis))

#define XRBT_ECTXT_UPDATE(xrbt_this, xrbt_ctxt)     \
            XSTD_ECTXT_UPDATE((xrbt_this), (xrbt_ctxt))

//====================================================================

#define XRBT_MAX_SIZE(xrbt_this)  \
    ((xrbt_size_t)(((xrbt_size_t)~0) / XRBT_ESIZE(xrbt_this)))

#define XRBT_RESET_NIL(xrbt_this)                           \
    do                                                      \
    {                                                       \
        (xrbt_this)->xnode_nil.xst_color    = XCLR_BLACK;   \
        (xrbt_this)->xnode_nil.xst_ksize    = 0;            \
        (xrbt_this)->xnode_nil.xrbt_owner   = (xrbt_this);  \
        (xrbt_this)->xnode_nil.xiter_parent =               \
        (xrbt_this)->xnode_nil.xiter_left   =               \
        (xrbt_this)->xnode_nil.xiter_right  =               \
            (xrbt_iter_t)(&(xrbt_this)->xnode_nil);         \
    } while (0)

#define XRBT_ITER_NIL(xrbt_this)     ((xrbt_iter_t)(&(xrbt_this)->xnode_nil))
#define XRBT_ITER_BEGIN(xrbt_this)   ((xrbt_this)->xiter_lnode)
#define XRBT_ITER_END(xrbt_this)     XRBT_ITER_NIL(xrbt_this)
#define XRBT_ITER_RBEGIN(xrbt_this)  ((xrbt_this)->xiter_rnode)
#define XRBT_ITER_REND(xrbt_this)    XRBT_ITER_NIL(xrbt_this)

#define XRBT_ITER_ELEM(xiter_node)   ((xrbt_elem_t)((xiter_node)->xrbt_elem))
#define XRBT_ITER_SWCLR(xiter_node)  ((xiter_node)->xst_color = !(xiter_node)->xst_color)
#define XRBT_ITER_ISNIL(xiter_node)  (0 == (xiter_node)->xst_ksize)
#define XRBT_ITER_NOTNIL(xiter_node) (0 != (xiter_node)->xst_ksize)

#define XRBT_ITER_ISDOCKED(xiter_node)            \
    ((XRBT_NULL != (xiter_node)->xiter_parent) && \
     (XRBT_NULL != (xiter_node)->xiter_left  ) && \
     (XRBT_NULL != (xiter_node)->xiter_right ))

#define XRBT_ITER_ISUNDOCKED(xiter_node)          \
    ((XRBT_NULL == (xiter_node)->xiter_parent) && \
     (XRBT_NULL == (xiter_node)->xiter_left  ) && \
     (XRBT_NULL == (xiter_node)->xiter_right ))   \

#define XRBT_ITER_UNDOCK(xiter_node)            \
    do                                          \
    {                                           \
        (xiter_node)->xiter_parent = XRBT_NULL; \
        (xiter_node)->xiter_left   = XRBT_NULL; \
        (xiter_node)->xiter_right  = XRBT_NULL; \
    } while (0)

#define XRBT_ELEM_LT(xrbt_this, xet_lptr, xet_rptr) \
    ((xrbt_this)->xfunc_kcmp((xet_lptr), (xet_rptr), XRBT_ECTXT(xrbt_this)))

//====================================================================

////////////////////////////////////////////////////////////////////////////////

#endif // __STD_RBTREE_INL__
